1. Field of the Invention
This invention relates generally to the field of data communications and more particularly to a method and apparatus for handling call signalling messages.
2. Description of the Related Prior Art
Communications networks support a multitude of communications between parties. Such communications include voice, data, video, multi-media, e-mail, etc. To initiate a communication, an originating party transmits a communication request, which includes the identity of the originating party, the identity of the destination party or parties, and the type of requested communication, to a local communication processing entity. The local communication processing entity determines, from the request, whether the originating party is authentic, whether it is authorized to access the requested type of communication, and whether the destination party is, or parties are, local to the local communication processing entity.
If the destination party is local, the local communication processing entity provides an incoming communication message to the destination party. The destination party responds to the incoming communication message with a communication connect message that is provided to the local communication processing entity. The local communication processing entity, in response to the communication connect message, establishes a communication path between the originating party and the destination party. In addition, the local communication processing entity supports the communication path until a communication end message is received. At this point, the local communication processing entity tears down the communication path.
If one or more of the destination parties is/are not local to the local communication processing entity, the local communication processing entity provides a connection communication setup message to the communication network. The communication network transports, via an intervening switch or a plurality of intervening switches, the communication setup message to a destination local communication processing entity that is affiliated with a destination party. The destination local communication processing entity provides the setup message to the destination party. In response, the destination party provides a communication connect message to the destination local communication processing entity. The destination local communication processing entity then provides the connect message to the originating local communication processing entity via the communication network. In turn, a communication path is established via the intervening switch or switches of the communication network between the originating and destination local processing entities.
Because the communication network can support a multitude of communications, any switch in the network may become overloaded. Such a switch may be a local communication processing entity and/or an intervening switch within the network. An overload condition may be caused by a burst of overhead data and/or a sustained amount of overhead data messages that exceeds the switch""s capacity. As is known, the overhead data messages include call set-up messages, connect messages, call proceeding messages, call release messages, release complete messages, and link layer information.
One technique to reduce the effects of overloading is to queue, in a first-in-first-out (FIFO) manner, incoming overhead data messages. While FIFO queuing works well for most burst conditions, it adds latency when the overload is a sustained overload. The latency can rise above a call set-up time and may even rise above a connect time out. As such, calls and/or set-up messages of calls are dropped.
Another technique for reducing the effects of overloading is to use a last-in-first-out (LIFO) queueing technique as specified in Bell Core TR-PSY-000505 issue 2, section 5.3.8, July 1987. As is known, in a LIFO queueing scheme, the longer an item remains in the queue the less likely it will get processed. But a newly received request (i.e. message), does not wait long unless it gets bumped for a newer message. As such, when the switch is in a sustained overload, some messages are dropped, but they are the oldest ones in the queue. If the dropped message is a call set-up message, the originating party""s request is dropped, requiring the originating party to resend the request. If the dropped message is a connect message, the call is dropped before a communication path is established, which wastes the processing efforts of the switch to establish the call up to this point. In addition, the communication path that was at least partially established, is unusable for other communications until a time out expires. Such a time out is typically ten seconds. If the dropped message is a release message, the links i.e. the communication resources, comprising the communication path are wasted i.e. unavailable for reallocation, until a thirty second time out expires. If the thirty second time out is also dropped, the communication resources are permanently hung up.
Another issue with LIFO queueing relates to multi-party calls and the addition of a party to a multi-party call. For such calls, the LIFO dequeuing process may not enqueue the multi-party call set-up messages in the proper order. As such, certain parties may not be added to the multi-party communication. For example, a typical multi-party communication is established by sending a message identifying a request for a multi-party communication and messages to add the parties. If an add party message is received before a multi-party communication message is received, the add party message will be dropped, thereby preventing the identified party from participating in the multi-party communication.
Yet another technique to reduce the effects of overloading is described in a United States application Ser. No. 09/246,612 filed on Feb. 8, 1999 and owned by Newbridge Networks Corporation, the contents of which are incorporated by reference herein. This application provides a method and apparatus for processing call signalling messages during burst overloading and sustained overloading of a communications switch. Such processing begins by receiving a plurality of call signalling messages, which may be call set-up messages, connect messages, call proceeding messages, call release messages, release complete messages, link layer information and other messages typically generated in the establishment of a call. As defined by the switch programmer, these messages may be designated as either, dispensable messages, indispensable messages or essential messages depending on the criticality of the message in establishing a call. For example, dispensable messages might be designated as those, that if dropped, have minimal impact on the efficiency of the communication switch, whereas essential messages would be categorized as those messages which evoke a time-out process to release whatever communication resources have been allocated to a particular communication set-up request. The processing then continues by comparing a queue occupancy level of a call processing queue with a first queue occupancy threshold. If the queue occupancy level compares unfavourably with the first queue occupancy threshold (e.g., the queue is storing more messages than desired), call signalling messages are enqueued into the call processing queue based on the types of the call signalling messages. For example, dispensable call signalling messages are enqueued in a last-in-first-out (LIFO) manner while indispensable and essential messages are enqueued in a first-in-first-out (FIFO) manner. With such a method and apparatus, burst and/or sustained overload conditions. in a communication switch are handled with reduced latency and without dropping call signalling messages that, when dropped, waste communication resources.
With this technique, when, for example, a Setup (dispensable) message arrives and the queue is in an overloaded state (the buffer size exceeds a fixed threshold) the incoming Setup message takes the position of the first Setup message in the queue, and this Setup message is then xe2x80x9cpushedxe2x80x9d (i.e. physically moved) to the next Setup message""s position. The pushing continues until the Setup with the greatest waiting time is reached. The last message is then dropped from the queue. As can be seen, one of the disadvantages of this technique is that it affects all of the Setup messages in the queue. Additionally, this technique does not guarantee that messages of a different type (dispensable, indispensable, or essential) will be queued and dequeued in the same chronological order. For example, if a Setup message is inserted into the queue before an essential message, it could be dequeued before or after the essential message, depending on the state of the queue. This behaviour is caused by the FIFO/LIFO queueing of dispensable messages. This behaviour could be problematic for some systems where the chronological order of the messages must be preserved. Finally, since the technique relies on thresholds based on queue occupancy levels it cannot address a situation where a given type remains in the queue beyond a desired time.
Therefore a need exists for a method and apparatus that provides higher throughput of call signalling messages during burst and overload conditions, while ensuring that message do not remain in the queue beyond a desired time.
The present invention seeks to overcome the deficiencies of the prior art by incorporating a latency based queueing algorithm into the proposed method and apparatus. The latency based queueing algorithm uses a threshold based on the-expected latency of the new incoming message to decide the queueing strategy to be adopted.
In accordance with a first embodiment of the present invention, there is defined a method of processing call signalling messages enqueued in a call processing queue, the call signalling messages including one or more dispensable, indispensable and essential messages, the method comprising the steps of: receiving a plurality of call signalling messages; determining the expected latency of the messages in the queue; comparing the expected latency with a predefined latency based threshold; when the expected latency compares favourably with the latency based threshold, enqueuing the plurality of call signalling messages in the queue; when the expected latency compares unfavourably with the latency based threshold, determining the queue occupancy level of the queue; comparing the queue occupancy level with a predefined queue occupancy threshold; and when the queue occupancy level compares unfavourably with the queue occupancy threshold, enqueuing the plurality of call signalling messages into the call processing queue based on the type of call signalling message.
In accordance with a second embodiment of the present invention, there is defined a call signal processing module comprising: a call processing queue; processing means; memory operably connected to the processing means, wherein the memory stores operational instructions that cause the processing means to: (i) receive a plurality of call signalling messages; (ii) determine the expected latency of messages in the queue; (iii) compare the expected latency with a predefined latency based threshold; (iv) when the expected latency compares favourably with the latency based threshold, enqueue the plurality of call signalling messages in the queue; (v) when the expected latency compares unfavourably with the latency based threshold, determine the queue occupancy level of the queue; (vi) compare the queue occupancy level with a predefined queue occupancy threshold; and (vii) when the queue occupancy level compares unfavourably with the queue occupancy threshold, enqueue the plurality of call signalling messages into the call processing queue based on the type of call signalling message.
In accordance with a third embodiment of the present invention, there is defined a computer-readable medium having stored thereon computer-executable instructions for performing the steps of: receiving a plurality of call signalling messages into a queue; determining the expected latency of messages in the queue; comparing the expected latency with a predefined latency based threshold; when the expected latency compares favourably with the latency based threshold, enqueuing the plurality of call signalling messages in the queue; when the expected latency compares unfavourably with the latency based threshold, determining the queue occupancy level of the queue; comparing the queue occupancy level with a predefined queue occupancy threshold; and when the queue occupancy level compares unfavourably with the queue occupancy threshold, enqueuing the plurality of call signalling messages into the call processing queue based on the type of call signalling message.
In accordance with a fourth embodiment of the present invention, there is defined a computer system for increasing the throughput of call signalling messages comprising: means for receiving a plurality of call signalling messages; means for storing said plurality of call signalling messages; means for processing the plurality of call signalling messages; and means for transmitting the plurality of call signalling messages, wherein the processing means operating on computer-executable instructions stored in the storage means determines the manner in which the call signalling messages will be processed utilizing two threshold tests performed sequentially, wherein the first test compares a new message expected latency to a latency based threshold and wherein the second test compares a queue occupancy level to a queue occupancy threshold.